package com.jeff.practice;

public class Test10 {

    public static void main(String[] args) {
        Test10 solution = new Test10();
        char[][] grid = {
                {'0', '0', '0', '0', '0'},
                {'1', '0', '0', '1', '1'},
                {'0', '0', '0', '0', '0'},
                {'0', '1', '1', '0', '0'},};
        System.out.println(solution.numIslands(grid)); // 输出: 3
    }

    public int numIslands(char[][] grid) {
        //首先判断边界条件
        if (grid == null || grid.length == 0) {
            return 0;
        }
        //定义遍历的行数和列数
        int rows = grid.length;
        int cols = grid[0].length;
        int islandCount = 0;
        //定义标记数组，用于记录是否访问过
        boolean[][] visited = new boolean[rows][cols];
        //遍历元素
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                //判断当前位置是否为岛屿，并且未被访问过
                if (grid[r][c] == '1' && !visited[r][c]) {
                    //深度优先搜索
                    dfs(grid, r, c, visited);
                    //岛屿数量加一
                    islandCount++;
                }
            }
        }

        return islandCount;
    }

    //定义深度优先搜索函数
    private void dfs(char[][] grid, int row, int col, boolean[][] visited) {
        //首先判断边界条件
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || visited[row][col] || grid[row][col] == '0') {
            return;
        }
        //标记当前位置为已访问
        visited[row][col] = true;
        //递归遍历当前位置的上下左右四个方向
        dfs(grid, row - 1, col, visited);//上
        dfs(grid, row + 1, col, visited);//下
        dfs(grid, row, col - 1, visited);//左
        dfs(grid, row, col + 1, visited);//右
    }
}
